package com.peng.leetcode.other;

import java.util.ArrayList;
import java.util.List;

/**
 * LongestPalindrome
 * <p>
 * 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
 *
 * @author: lupeng6
 * @create: 2020/10/15 16:40
 */
public class LongestPalindrome {


    public static void main(String[] args) {
//        System.out.println(new Solution1().longestPalindrome("babad"));
//        System.out.println(new DpSolution().longestPalindrome("babad"));
        System.out.println(new DpSolution().longestPalindrome("aaaa"));
    }


    static class Solution {
        public String longestPalindrome(String s) {
            if (s.length() < 2) {
                return s;
            }

            List<String> strs = new ArrayList<String>();

            for (int i = 0; i < s.length(); i++) {
                for (int j = i + 1; j <= s.length(); j++) {
                    strs.add(s.substring(i, j));
                }
            }

            int maxLength = 0;
            String ret = null;

            for (String str : strs) {
                int startIndex = 0;
                int endIndex = str.length() - 1;
                while (true) {
                    if (startIndex < endIndex) {
                        if (Character.valueOf(str.charAt(startIndex)).equals(str.charAt(endIndex))) {
                            startIndex++;
                            endIndex--;
                        } else {
                            break;
                        }
                    } else if (startIndex >= endIndex) {
                        if (str.length() > maxLength) {
                            ret = str;
                            maxLength = str.length();
                        }
                        break;
                    }
                }
            }

            return ret;
        }
    }


    static class Solution1 {
        public String longestPalindrome(String s) {
            if (s == null || s.length() < 0) {
                return "";
            }
            int start = 0;
            int end = 0;
            for (int i = 0; i < s.length(); i++) {
                int len1 = expandAroundCenter(s, i, i);
                int len2 = expandAroundCenter(s, i, i + 1);
                int maxLen = Math.max(len1, len2);
                if (maxLen > (end - start)) {
                    start = i - (maxLen - 1) / 2;
                    end = i + maxLen / 2;
                }
            }
            return s.substring(start, end + 1);
        }

        public static int expandAroundCenter(String source, int left, int right) {
            if (left < 0 || right >= source.length() || source.charAt(left) != source.charAt(right)) {
                return 0;
            }

            while (left >= 0 && right < source.length() && (source.charAt(left) == source.charAt(right))) {
                left--;
                right++;
            }

            return right - left - 1;
        }
    }


    /**
     * 动态规划解回文子串 
     *
     * @author lupeng6
     * @date 2021/1/2 20:24
     */
    static class DpSolution {
        public String longestPalindrome(String s) {
            if (s.length() < 2) {
                return s;
            }
            int maxLength = 1;
            int start = 0;
            int end = 1;
            int length = s.length();
            boolean[][] dp = new boolean[length][length];
            for (int i = 0; i < length; i++) {
                dp[i][i] = true;
            }
            for (int i = 1; i < length; i++) {
                for (int j = 0; j < i; j++) {
                    if (s.charAt(i) != s.charAt(j)) {
                        dp[i][j] = false;
                        continue;
                    }
                    // s.charAt(i) == s.charAt(j)
                    if ((i - j + 1) == 2) {
                        dp[i][j] = true;
                        if ((i - j + 1) > maxLength) {
                            maxLength = (i - j + 1);
                            start = j;
                            end = i;
                        }
                        continue;
                    }
                    // (i - j + 1) > 2
                    if (dp[i - 1][j + 1]) {
                        dp[i][j] = true;
                        if ((i - j + 1) > maxLength) {
                            maxLength = (i - j + 1);
                            start = j;
                            end = i;
                        }
                    } else {
                        dp[i][j] = false;
                    }
                }
            }
            if (maxLength > 1) {
                return s.substring(start, end + 1);
            } else {
                return s.charAt(0) + "";
            }
        }
    }
}
